'''
1. 每个节点不仅仅是需要遍历上下左右，而且是四个方向的深度优先遍历
所有的元素都需要做这个深度优先搜索遍历！！！
2. 回溯的时候需要动态的标记访问过的节点！标记完访问过的节点之后呢，
'''
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            # 节约栈空间
            tmp, board[i][j] = board[i][j], '/'
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            #  因为只代表此次搜索过程中，该元素已访问过，当初始i j变化时，又开始了另一次搜索过程
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        def dfs(i,j,k):
            # 结束条件有两个
            # if i>m-1 or j>n-1 or board[i][j] != word[k]: return False
            # Line 7: IndexError: list index out of range
            # 因为有可能小于0

            if not 0 <= i < m or not 0 <= j < n or board[i][j] != word[k]: return False
            if k == len(word) -1: return True
            # 避免重复拓展节点
            temp, board[i][j] = board[i][j], '/'
            res = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            board[i][j] = temp
            return res
        for i in range(m):
            for j in range(n):
                if dfs(i,j,0): return True
        return False
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        def dfs(i,j,k):
            if i >= m or j >=n or board[i][j] != word[k]: return False
            if k == len(word) -1: return True
            tmp, board[i][j] = board[i][j], '/'
            res = dfs(i+1,j,k+1) or dfs(i-1,j,k+1) or dfs(i,j+1,k+1) or dfs(i,j-1,k+1)
            board[i][j] = tmp
            return res
        for i in range(m):
            for j in range(n):
                if dfs(i,j,0): return True
        return False
